{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 样本采样与特征采样\n",
    "类似于randomforest，xgboost也可进行bootstrap的样本采样，和随机列采样，以增强模型的泛化能力，避免过拟合\n",
    "\n",
    "### 稀疏/缺失值处理\n",
    "\n",
    "xgboost会为稀疏/缺失值选择一个默认方向，如果训练集中有稀疏/缺失值，通过计算其增益来选择往左还是往右作为默认方向，如果训练集中没有，则选择往右为默认方向\n",
    "\n",
    "### 直方图算法：快速切分点查找\n",
    "在构建树时，最重要的操作便是特征及其对应的切分阈值的查找，CART一般选择一种精确的贪心搜索，即遍历所有的特征及其所有可能的取值情况，这非常耗时，xgboost采用了直方图优化策略，具体操作其实很简单，就是对数据做了一个分箱的操作，如下图，将8个连续数值分成了两组，分组前有7个切分点需要搜索，而分组后只有一个切分点，而对于更加一般的情况，连续值的取值情况往往要多的多，分组操作将极大的提高搜索速度，而且还能在一定程度上防止过拟合   \n",
    "\n",
    "\n",
    "![avatar](./source/10_直方图算法.png)   \n",
    "\n",
    "而且分箱操作还能在存储和计算上带来**好处**：   \n",
    "\n",
    "（1）存储上，之前需要使用float类型，而分箱后只需要使用int类型，内存使用缩小为$\\frac{1}{8}$；   \n",
    "\n",
    "（2）计算上也可以做优化，比如需要计算右孩子节点的直方图分布，只需使用父节点的直方图分布减去左孩子的直方图分布即可，无需再次统计  \n",
    "\n",
    "另外分箱还有两种**策略**，全局策略和本地策略：  \n",
    "\n",
    "（1）全局策略：全局只做一次分箱操作；   \n",
    "\n",
    "（2）本地策略：每个节点在分裂时，都会重新做一次分箱操作；  \n",
    "\n",
    "全局策略操作简单，而本地策略可能取得更好的精度；上面的分箱操作其实是分位数查找法，xgboost还有**其他的分位数查找法**：   \n",
    "\n",
    "（1）误差分位数法：对于数据量太大的情况，没法直接将所有特征取值加载进内容，所以没法精确的求解分位点，[该算法>>>](http://www.mathcs.emory.edu/~cheung/Courses/584-StreamDB/Syllabus/08-Quantile/Greenwald.html#proofprop1)构造了一种数据，可以以一定误差保存流式数据的分位点；它的优化版本：A fast algorithm for approximate quantiles in high speed data streams  被用于xgboost中   \n",
    "\n",
    "（2）加权分位数法：基本思想是，如果样本的预测结果越不稳定，则需要更细的切分粒度，而二阶导可以用来衡量预测结果的不稳定性，二阶导绝对值越大的样本点越需要被细分"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### leaf-wise vs level-wise\n",
    "leaf-wise和level-wise是树的两种生成策略，如下图所示，level-wise是逐层生成决策树，而leaf-wise是按需生成决策树，如果切分后某子节点的收益较低，则不会生成该子节点，这极大的提升了训练速度\n",
    "\n",
    "![avatar](./source/10_level_wise_vs_leaf_wise.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 系统层面的优化\n",
    "\n",
    "这部分内容简略介绍，主要有稀疏数据列压缩、缓存感知访问、外存块计算优化、分布式计算、GPU加速\n",
    "\n",
    "#### 稀疏数据列压缩\n",
    "\n",
    "xgboost会对稀疏数据进行列压缩（Compressed Sparse Column,CSC），这可以提高**特征值排序**的效率，方便节点分裂时的特征选择\n",
    "\n",
    "#### 缓存感知访问\n",
    "\n",
    "由于每个特征其特征值的排序不同，再对一阶、二阶导数的提取时，会有非连续内存访问的问题，将这些数据放入**CPU缓存**可以提高计算的效率，具体做法是把某些连续有序的mini-batch数据的统计值缓存到CPU缓存，这样其他特征在做特征选择时，有可能命中这部分数据\n",
    "\n",
    "#### 外存块计算优化\n",
    "\n",
    "整个特征选择的过程其实是按“列”进行的，也就是说对某列进行操作时，其他的列其实并没有被使用（lable除外），所以树的训练过程并不用将所有数据加载到内存，而是可以按需载入，这部分可以分两个线程来做：一个线程负责计算，另一线性负责数据读取\n",
    "\n",
    "#### 分布式计算\n",
    "\n",
    "目前xgboost在主流的分布式计算平台上均有实现，比如spark,flink等\n",
    "\n",
    "#### GPU加速\n",
    "\n",
    "xgboost在按level-wise方式生成树时可以通过gpu提速，通过gpu可以同时对一层的数据进行处理，从而提高最优切分点的查找效率；而节点的桶排序也可通过CUDA原句实现的基数排序优化"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
